Images may be represented as two-dimensional matrices of picture elements, or pixels. The spatial resolution and intensity level of each pixel are chosen to correspond to the type of output device being used. For example, computer monitors may display images at 75 dots per inch (DPI), and have 256 levels of intensity for each color component. Such monitors usually use the additive primary color components, red, green, and blue (RGB), which can be combined to produce millions of colors, as well as black. Pixels having more than two levels of intensity for each color component are referred to herein as image pixels.
However, image-forming devices that output onto media, such as ink-jet printers and laser printers, may be binary devices. In binary devices, for each pixel location on the printed medium, the device can print at two levels for each color component, on or off. The pixels output by such image-forming devices are referred to herein as output pixels. In binary devices, Image pixels, having more than two levels of intensity for each color component, are therefore converted to output pixels, having only two levels of intensity for each color component, prior to their output by image-forming devices onto media. Such conversion is commonly referred to as halftoning.
One halftoning approach is known as error diffusion. In error diffusion, for each color of an image pixel, the decision to output a corresponding output pixel by the image-forming device is based on the intensity level of the color component of the image pixel, as well as the output pixels output for the previous image pixels. Error diffusion tries to distribute output pixels so as to reduce pixel overlap, reduce empty space between output pixels, and otherwise create eye-pleasing patterns. However, at least some such approaches, such as plane-dependent halftoning, are usually successful only for colors of similar darkness, leading lead to unpleasant patterns for colors of varying darkness.